package practice_2025_7_17;

import java.util.*;

public class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m = 0;
    int n = 0;

    /**
     * 岛屿的最大面积
     * @param grid
     * @return
     */
    public int maxAreaOfIsland(int[][] grid) {
        List<int[]> list = new ArrayList<>();

        m = grid.length;
        n = grid[0].length;
        int max = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    max = Math.max(max, bfs(grid, i, j));
                }
            }
        }
        return max;
    }

    public int bfs(int[][] grid, int x, int y) {
        int count = 1;
        grid[x][y] = 0;
        for(int i = 0; i < dx.length; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && grid[nextX][nextY] == 1) {
                count += bfs(grid, nextX, nextY);
            }
        }
        return count;
    }

    /**
     * 被围绕的区域
     * @param board
     */
    public void solve(char[][] board) {
        // 将环绕区域 O 修改为 X
        m = board.length;
        n = board[0].length;
        char src = 'O';
        char target = '*';
        for(int i = 0; i < m; i++) {
            if (board[i][0] == src) {
                bfs(board, i, 0, src, target);
            }
            if (board[i][n - 1] == src) {
                bfs(board, i, n - 1, src, target);
            }
        }
        for(int j = 0; j < n; j++) {
            if (board[0][j] == src) {
                bfs(board, 0, j, src, target);
            }
            if (board[m - 1][j] == src) {
                bfs(board, m - 1, j, src, target);
            }
        }
        src = 'O';
        target = 'X';
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (board[i][j] == src) {
                    bfs(board, i, j, src, target);
                }
            }
        }
        src = '*';
        target = 'O';
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (board[i][j] == src) {
                    bfs(board, i, j, src, target);
                }
            }
        }
    }
    public void bfs(char[][] board, int x, int y, char src, char target) {
        board[x][y] = target;
        for(int i = 0; i < dx.length; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && board[nextX][nextY] == src) {
                bfs(board, nextX, nextY, src, target);
            }
        }
    }

    /**
     * 迷宫中离入口最近的出口
     * @param maze
     * @param entrance
     * @return
     */
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        String str = "abc";
        int n = maze[0].length;
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        int x = entrance[0];
        int y = entrance[1];
        int count = 0;
        vis[x][y] = true;
        for(int i = 0; i < dx.length; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < m &&
                    nextY >= 0 && nextY < n &&
                    (!vis[nextX][nextY]) &&
                    maze[nextX][nextY] == '.') {
                vis[nextX][nextY] = true;
                queue.add(new int[]{nextX, nextY});
            }
        }
        count++;
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                int[] tmp = queue.poll();
                x = tmp[0];
                y = tmp[1];
                // 判断当前是否已到出口
                if (x == 0 || x == m - 1 || y == 0 || y == n - 1) {
                    return count;
                }
                // 未到出口, 继续向外走
                for(int i = 0; i < dx.length; i++) {
                    int nextX = x + dx[i];
                    int nextY = y + dy[i];
                    if (nextX >= 0 && nextX < m &&
                            nextY >= 0 && nextY < n &&
                            (!vis[nextX][nextY]) &&
                            maze[nextX][nextY] == '.') {
                        vis[nextX][nextY] = true;
                        queue.add(new int[]{nextX, nextY});
                    }
                }
            }
            count++;
        }
        return -1;
    }


    /**
     * 单词接龙
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 返回最短转换序列
        // 转换序列中必须包含 endWord
        // 关键: 如何找到下一个单词 -> 一个一个计算
        Set<String> word = new HashSet<>();
        Set<String> vis = new HashSet<>();
        for(String str: wordList) {
            word.add(str);
        }
        if (!word.contains(endWord)) {
            return 0;
        }
        int count = 0;
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        vis.add(beginWord);
        while(!queue.isEmpty()) {
            int sz = queue.size();
            count++;
            while(sz-- > 0) {
                String str = queue.poll();
                if (str.equals(endWord)) {
                    return count;
                }
                char[] chs = str.toCharArray();
                for(int i = 0; i < chs.length; i++) {
                    char tmp = chs[i];
                    for(char j = 'a'; j <= 'z'; j++) {
                        chs[i] = j;
                        String next = new String(chs);
                        if (word.contains(next) && (!vis.contains(next))) {
                            //  System.out.println(next + " " );
                            queue.add(next);
                            vis.add(next);
                        }
                    }
                    chs[i] = tmp;
                }
            }
        }
        return 0;
    }


    /**
     * 为高尔夫比赛砍树
     * @param forest
     * @return
     */
    public int cutOffTree(List<List<Integer>> forest) {
        // 0 -> 障碍
        // 1 -> 地面
        // >1 -> 树
        // 按树的高度, 从高到低开始砍
        // 先找到要砍的第一颗树 -> 开始砍树
        // 从低到高排序 -> 再从低到高砍树 -> 依次找最短路径
        m = forest.size();
        n = forest.get(0).size();
        int[][] f = new int[m][n];
        List<int[]> target = new ArrayList<>();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                f[i][j] = forest.get(i).get(j);
                if (f[i][j] > 1) {
                    target.add(new int[]{f[i][j], i, j});
                }
            }
        }
        // 对树的高度进行排序
        Collections.sort(target, Comparator.comparingInt(v -> v[0]));
        // for(int i = 0; i < target.size(); i++) {
        //     System.out.println(target.get(i)[0]);
        // }
        // 依次砍树
        int sum = 0;
        for(int i = 0; i < target.size(); i++) {
            int count = 0;
            if (i == 0) {
                count = finMinCount(f, 0, 0, target.get(i)[1],target.get(i)[2]);
            } else {
                count = finMinCount(f, target.get(i - 1)[1], target.get(i - 1)[2], target.get(i)[1], target.get(i)[2]);
            }
            if (count == -1) {
                return -1;
            }
            // System.out.println("tar: " + target.get(i)[1] + " " +  target.get(i)[2] + " count: " + count);
            sum += count;
        }
        return sum;
    }

    /**
     从 (x, y) 到 (tarX, tarY) 的最短路径
     */
    public int finMinCount(int[][] f, int x, int y, int tarX, int tarY) {
        boolean[][] vis = new boolean[m][n];
        vis[x][y] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        int count = 0;
        while(!queue.isEmpty()) {
            int sz = queue.size();
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                x = tmp[0];
                y = tmp[1];
                if (x == tarX && y == tarY) {
                    return count;
                }
                for(int i = 0; i < dx.length; i++) {
                    int nextX = x + dx[i];
                    int nextY = y + dy[i];
                    if (nextX >= 0 && nextX < m &&
                            nextY >= 0 && nextY < n &&
                            !vis[nextX][nextY] &&
                            f[nextX][nextY] > 0) {
                        vis[nextX][nextY] = true;
                        queue.add(new int[]{nextX, nextY});
                    }
                }
            }
            count++;
        }
        return -1;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] maze = {
                {'.', '.', '.', '.', '.', '.', '.', '+', '.'},
                {'.', '+', '.', '.', '.', '+', '.', '+', '+'},
                {'.', '.', '.', '.', '+', '.', '.', '.', '.'},
                {'.', '.', '+', '.', '.', '+', '.', '.', '.'},
                {'+', '.', '.', '+', '.', '.', '.', '.', '+'},
                {'.', '+', '.', '.', '.', '+', '.', '.', '.'},
                {'.', '.', '+', '.', '.', '.', '+', '.', '.'},
                {'.', '.', '+', '+', '+', '+', '+', '.', '.'},
                {'.', '+', '+', '.', '.', '+', '.', '.', '.'}
        };
        int[][] array = {
                {1, 2, 3},
                {0, 0, 4},
                {7, 6, 5}
        };
        // 创建 List<List<Integer>>
        List<List<Integer>> forest = new ArrayList<>();

        for (int[] row : array) {
            List<Integer> listRow = new ArrayList<>();
            for (int val : row) {
                listRow.add(val);
            }
            forest.add(listRow);
        }
        solution.cutOffTree(forest);
        solution.nearestExit(maze, new int[]{0, 1});
    }
}
